class Solution {
public:
    vector<int> father,size;
    int find(int x){
        if(x != father[x]){
            father[x] = find(father[x]);
        }
        return father[x];
    }
    void Union(int u,int v){
        int x = find(u);
        int y = find(v);
        if(x == y) return;
        father[y] = x;
        size[x] += size[y];
    }
    
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int n = graph.size();
        int m = initial.size();
        sort(initial.begin(),initial.end());
        
        father.resize(n);
        size.resize(n,1);
        
        for(int i = 0;i < n;i++){
            father[i] = i;
        }

        for(int i = 0;i < n;i++){
            if(count(initial.begin(),initial.end(),i)){
                continue;
            }
            for(int j = i + 1;j < n;j++){
                if(count(initial.begin(),initial.end(),j)){
                    continue;
                }
                if(graph[i][j] == 1){
                    Union(i,j);
                }
            }
        }
        

        vector<int> fectInt(n,-1);
        for(int& i : initial){
            for(int j = 0;j < n;j++){
                if(count(initial.begin(),initial.end(),j)){
                    continue;
                }
                int y = find(j);
                if(graph[i][j] == 0 || fectInt[y] == -2) continue;
                
                if(fectInt[y] == -1){
                    fectInt[y] = i;
                }else if(fectInt[y] != i){
                    fectInt[y] = -2;
                }
            }
        }
        
        vector<int> fectNum(n);
        for(int i = 0;i < n;i++){
            if(fectInt[i] != -1 && fectInt[i] != -2){
                fectNum[fectInt[i]] += size[i];
            }
        }
            
         int Max = -1; 
        int ret = initial[0];
        for(int& i : initial){
            if(fectNum[i] > Max){
                Max = fectNum[i];
                ret = i;
            }
        }
            return ret;
    }
};
